<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Ford Fulkerson Algorithm Edmonds Karp Algorithm For Max Flow</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="ford-fulkerson-algorithm-edmonds-karp-algorithm-for-max-flow">Ford Fulkerson Algorithm Edmonds Karp Algorithm For Max Flow</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=GiN3jRdgxU4&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=11">https://www.youtube.com/watch?v=GiN3jRdgxU4&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=11</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java</a></li>
</ul>
<p>需要多次做BFS遍历， 每找到一条路径， 就做反向修改。</p>
<p>下面是初始状态，需要寻找 A -&gt; G 的最大流量</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\ford0.png" alt="ford0.png"></p>
<p>下图,第1次遍历  A -&gt; D -&gt; E -&gt; G = 1</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\ford1.png" alt="ford1.png"></p>
<p>下图,第2次遍历  A -&gt; D -&gt; F -&gt; G = 2</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\ford2.png" alt="ford2.png"></p>
<p>下图,第3次遍历  A -&gt; B -&gt; C -&gt; D -&gt; F -&gt; G = 1</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\ford3.png" alt="ford3.png"></p>
<p>下图,第4次遍历  A -&gt; B -&gt; C -&gt; E -&gt; D -&gt; F -&gt; G = 1</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\ford4.png" alt="ford4.png"></p>
<p>总流量  1+2+1+1 = 4</p>

    </body>
    </html>